#include <iostream>
#include <vector>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

//class Solution {
//public:
//    ListNode* partition(ListNode* head, int x) {
//        if (head == nullptr)
//        {
//            return nullptr;
//        }
//        ListNode* min_val = nullptr;
//        ListNode* max_val = nullptr;
//        ListNode* newhead = nullptr;
//        ListNode* maxhead = nullptr;
//        ListNode* tail = head;
//        while (tail)
//        {
//            if (tail->val < x)
//            {
//                if (min_val == nullptr)
//                {
//                    newhead = min_val = tail;
//                }
//                else
//                {
//                    min_val->next = tail;
//                    min_val = tail;
//                }
//            }
//            else
//            {
//                if (max_val == nullptr)
//                {
//                    maxhead = max_val = tail;
//                }
//                else
//                {
//                    max_val->next = tail;
//                    max_val = tail;
//                }
//            }
//            tail = tail->next;
//        }
//        if (max_val != nullptr)
//        {
//            max_val->next = nullptr;
//        }
//        if (newhead == nullptr)
//        {
//            return maxhead;
//        }
//        min_val->next = maxhead;
//        return newhead;
//    }
//};
//
//class Solution {
//public:
//    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//        if (root == nullptr)
//        {
//            return nullptr;
//        }
//        if (root == p || root == q)
//        {
//            return root;
//        }
//        TreeNode* left = lowestCommonAncestor(root->left, p, q);
//        TreeNode* right = lowestCommonAncestor(root->right, p, q);
//        if (left && right)
//        {
//            return root;
//        }
//        else if (left != nullptr)
//        {
//            return left;
//        }
//        else if (right != nullptr)
//        {
//            return right;
//        }
//        return nullptr;
//    }
//};
//
//class Solution {
//public:
//    int countNodes(TreeNode* root) {
//        if (root == nullptr)
//        {
//            return 0;
//        }
//        return countNodes(root->left) + countNodes(root->right) + 1;
//    }
//};
//
//class Solution {
//public:
//    bool hasPathSum(TreeNode* root, int targetSum) {
//        if (root == nullptr)
//        {
//            return false;
//        }
//        sum += root->val;
//        if (sum == targetSum && root->left == nullptr && root->right == nullptr)
//        {
//            return true;
//        }
//        if (hasPathSum(root->left, targetSum))
//        {
//            return true;
//        }
//        if (hasPathSum(root->right, targetSum))
//        {
//            return true;
//        }
//        sum -= root->val;
//        return false;
//    }
//    int sum = 0;
//};

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* building(vector<int>& preorder, vector<int>& inorder, int p1, int p2)
    {
        if (p1 > p2 || p2 >= size(inorder))
        {
            return nullptr;
        }
        int i = p1;
        while (i < size(inorder) && preorder[p1] != inorder[i])
        {
            i++;
        }
        TreeNode* root = new TreeNode(preorder[p1]);
        root->left = building(preorder, inorder, p1 + 1, i - p1);
        root->right = building(preorder, inorder, p1 + i, i + 1);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        if (n == 0)
        {
            return nullptr;
        }
        TreeNode* root = building(preorder, inorder, 0, 0);
        return root;
    }
    void Print(TreeNode* root)
    {
        if (root == nullptr)
        {
            cout << "NULL ";
            return;
        }
        cout << root->val << " ";
        Print(root->left);
        Print(root->right);
    }
};

int main()
{
    vector<int> preorder = { 3,9,20,15,7 };
    vector<int> inorder = { 9,3,15,20,7 };
    Solution s;
    TreeNode* new_Tree = s.buildTree(preorder, inorder);
    s.Print(new_Tree);
    return 0;
}